Despite general promulgation and healthy acceptance of the concept of chip cards on the part of the public, most practical applications appeared only a few years ago principally owing to the limitations in the computational power of the cards. Progress in the sphere of non-volatile storage capacity of information, security and circuit technology (for example the EEPROM) encourage the rapid emergence of new generations of cards and of ever more ambitious applications such as the new American Digital Signature Standard (DSA).
The Digital Signature Standard (DSA) was proposed by the U.S. National Institute of Standards and Technology so as to provide an appropriate basis for applications requiring digital signatures instead of conventional signatures. A DSA signature is a pair of large numbers represented in a computer by strings of binary digits. The digital signature is computed with the aid of a series of computational rules (the DSA) and a set of parameters in such a way as to make it possible to certify both the identity of the signatory and the integrity of the data. The DSA makes it possible to generate and verify signatures.
The process for generating signatures makes use of a private key to produce a digital signature. The verification process uses a public key which corresponds to the secret key without however being identical to it. Each user possesses a pair of keys (public, secret). It is assumed that the public keys are known to everyone, whilst the secret keys are never disclosed. Anybody has the capacity to verify the signature of a user by using his public key but signatures cannot be generated other than by using the secret key of the user.
It will be recalled that the parameters of the DSA algorithm are:
1 A prime p such that PA0 2 A prime q such that PA0 3 A number g, of order q modulo p such that ##EQU1## mod p, where h is any integer satisfying 1&lt;h&lt;p-1 and ##EQU2## mod p&gt;1. 4 A number x, generated randomly or pseudo-randomly. PA0 5 A number y defined by the relation: y=g.sup.x mod p. PA0 6 A number k generated randomly or pseudo-randomly such that 0&lt;k&lt;q. PA0 For example, if q=5 and k=3 then ##EQU4## since 3.times.2=6=1 mod 5. PA0 1 ##EQU5## mod q 2 u.sub.1 =m w mod q PA0 3 u.sub.2 =r w mod q PA0 4 v=(g.sup.u1 y.sup.u2 mod p) mod q PA0 5 And compares whether v and r are equal so as to accept or reject the signature. PA0 1 The authority draws a random number J of Z1 bytes (in practice Z1 will be less than or equal to 20 bytes. We have preferentially chosen Z1=8). PA0 2 The authority expands J to obtain a number i of Z2 bytes, Z2 being greater than or equal to Z1 (we have chosen preferentially Z2=20) PA0 3 The authority computes c=DES (card.sub.-- key, J) PA0 4 The authority back-computes ##EQU6## mod q 5 The authority computes r=(g.sup.k mod p) mod q PA0 6 The authority sends c and r to the card PA0 7 The card computes J=DES.sup.-1 (card.sub.-- key, c) PA0 8 The card records J and r in EPROM (or EEPROM) PA0 1 The card extracts J and r from the EPROM (or EEPROM) PA0 2 The card expands J to obtain i on Z2 bytes PA0 3 The card receives the message m from the verifier PA0 4 The card computes s=(m+x r) i mod q PA0 5 The card sends s and r to the verifier and invalidates the pair {r, J}, deleting it from the EEPROM. PA0 1 The card draws a random number J of Z1 bytes (preferably 10 bytes) PA0 2 The card sends J to the authority PA0 3 The authority computes ##EQU7## mod q 4 The authority computes r=(g.sup.k mod p) mod q PA0 5 The authority sends r to the card PA0 6 The card records J and r in EPROM (or EEPROM). PA0 1 The card extracts J and r from the EPROM (or EEPROM) PA0 2 The card receives the message m from the verifier PA0 3 The card computes s=(m+x r) SHA(x, J) mod q PA0 4 The card sends s and r to the verifier and invalidates the pair {r, J}, deleting it from the EEPROM. PA0 1 The card draws a random number J of Z1 bytes (preferably 10 bytes) and records it in EPROM (or EEPROM) PA0 2 The card sends J to the authority PA0 3 The authority computes k.sub.i for i=1 to n, where n represents the number of coupons to be loaded as follows: PA0 5 The authority sends the r.sub.i to the card PA0 6 The card records the r.sub.i in EPROM (or EEPROM). PA0 1 The card extracts J and an r.sub.i from the EPROM (or EEPROM) PA0 2 The card receives the message m from the verifier PA0 3 The card computes s=(m+x r.sub.i) SHA(x, J, i) mod q PA0 4 The card sends s and r.sub.i to the verifier and invalidates r.sub.i deleting it from the EEPROM. PA0 1 Two primes p and q such that q.vertline.p-1, q.gtoreq.2.sup.140, p.gtoreq.2.sup.512, PA0 2 A number .alpha. of order q modulo p, that is to say satisfying .alpha..sup.q =1 (mod p), .alpha..noteq.1 PA0 3 A one-way hashing function (for example the SHA) PA0 4 A number s generated randomly or pseudo-randomly PA0 5 A number v defined by the relation: v=.alpha..sup.-s mod p PA0 1 The card draws a random number J of Z1 bytes (preferably 10 bytes) and records it in EPROM (or EEPROM) PA0 2 The card sends J to the authority PA0 3 The authority computes the x.sub.i for i=1 to n, with n the number of coupons to be loaded as follows: PA0 4 The authority sends the x.sub.i to the card PA0 5 The card records the x.sub.i in EPROM (or EEPROM). PA0 1 The card extracts J and an x.sub.i from the EPROM (or EEPROM) PA0 2 The card receives the message m from the verifier PA0 3 The card computes e=SHA(m, s) mod q PA0 4 The card computes y=SHA(s, J, i)+se mod q PA0 4 The card sends x.sub.i and y to the verifier and invalidates the coupon {x.sub.i }, deleting it from the EEPROM. PA0 1 The card extracts r and k from the EEPROM (or EPROM) PA0 2 The card receives the message m from the verifier PA0 3 The card computes ##EQU9## mod q 4 The card sends r and s to the verifier and invalidates r, deleting it from the EEPROM PA0 5 While the verifier is verifying the validity of the pair {r, s}, the card draws a new random number k of 20 bytes and back-computes, computes r=(g.sup.k mod p) mod q and overwrites the EPROM (or EEPROM) with the new coupon {r, k}. PA0 1 The authority computes, for b=1 to n: PA0 2 The authority computes: PA0 3 The authority sends the n coupons to the card. PA0 1 The card generates a random number J, records it in EPROM (or EEPROM) and sends it to the authority PA0 2 The authority computes, for b=1 to n: ##EQU11## mod q PA0 3 The authority computes: PA0 4 The authority sends the values r.sub.b of the n coupons to the card which records them in EPROM (or EEPROM) after J. PA0 (R,S)=DSS.sub.AUTHORITY SHA(Control.sub.-- Datum, r.sub.1, . . . r.sub.n)). PA0 1 The card draws a random number J of Z1 bytes (10 bytes) and records it in EPROM (or EEPROM) PA0 2 The card sends J to the authority PA0 3 The authority computes the k.sub.i for i=1 to n, with n the number of coupons to be loaded, and the corresponding ri [sic], as follows: PA0 4 The authority computes the Certificate (R, S) corresponding to the n coupons: PA0 6 The card records the Certificate (R,S), the control data and the r.sub.i in non-volatile memory EPROM (or EEPROM). PA0 1 The card extracts J and an r.sub.i from the EPROM (or EEPROM) PA0 2 The card receives the message m from the verifier PA0 3 The card computes s=(m+x r.sub.i) SHA(x,J,i) mod q PA0 4 The card sends s, r.sub.i, the Certificate and the data required for its verification to the verifier and invalidates r.sub.i, deleting it from the EEPROM.
2.sup.L-1 &lt;p&lt;2.sup.L for 512.ltoreq.L.ltoreq.1024 and L=64 .alpha. for any .alpha..
2.sup.159 &lt;q&lt;2.sup.160 and p-1 is a multiple of q.
The integers p, q and g are given parameters of the system which may be published and/or shared by a group of users. The secret and public keys of a signatory are x and y respectively. The parameters x and k are used for the generation of the signature and must be kept secret. The parameter k must be regenerated for each signature.
In order to sign a message m (hash value of an initial file M), the signatory computes the signature {r, 2} by:
r=(g.sup.k mod p) mod q and ##EQU3## mod q Where the division by k is understood as modulo q (i.e. 1/k is the number k' such that k k'=1 mod q).
After having tested that r.noteq.0.noteq.s, as explained in the description of the DSA, the signature {r, s} is sent to the verifier which computes: